package com.leetcode;

import ds.ListNode;

import java.util.LinkedList;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No445
 * @description leetcode 445 两数相加 II
 * @date 2021/1/26 下午3:08
 */
public class No445 {
    public static void main(String[] args) {
        ListNode l10 = new ListNode(7);
        ListNode l11 = new ListNode(2);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(3);
        l10.next = l11;
        l11.next = l12;
        l12.next = l13;

        ListNode l21 = new ListNode(5);
        ListNode l22 = new ListNode(6);
        ListNode l23 = new ListNode(4);
        l21.next = l22;
        l22.next = l23;

        ListNode res = addTwoNumbers(l10,l21);
        printListNode(res);
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        // 使用Linkedlist模拟栈
        LinkedList<Integer> stack1 = new LinkedList<>();
        LinkedList<Integer> stack2 = new LinkedList<>();
        while (l1 != null) {
            stack1.addLast(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.addLast(l2.val);
            l2 = l2.next;
        }
        int curry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || curry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.removeLast();
            int b = stack2.isEmpty() ? 0 : stack2.removeLast();
            int sum = a + b + curry;
            ListNode temp = new ListNode(sum % 10);
            temp.next = cur.next;
            cur.next = temp;
            curry = sum / 10;
        }
        return res.next;
    }

    public static void printListNode(ListNode l){
        if(l == null){
            System.out.println("empty listnode");
        }else{
            while (l != null){
                System.out.print(l.val);
                System.out.print( " ");
                l = l .next;
            }
        }
    }

}
